package com.frank.tree;

public class Test {

	@org.junit.Test
	public void testBinarySearch() {

		// 二分查找需先排好序
		int[] array = new int[] { 1, 2, 4, 9, 13, 20, 22, 29, 34, 35 };
		int key = 34;
		System.out.println(binarySearch(array, 0, array.length, key));
	}

	/**
	 * 二分查找法
	 * 
	 * @param array
	 *            查找的数组
	 * @param fromIndex
	 *            开始的位置
	 * @param toIndex
	 *            到达的位置
	 * @param key
	 *            需要查找的值
	 */
	public static int binarySearch(int[] array, int fromIndex, int toIndex,
			int key) {
		int low = fromIndex;
		int high = toIndex - 1;
		while (low <= high) {
			// 无符号除以2
			int mid = (low + high) >>> 1;
			int midVal = array[mid];
			if (midVal < key) {
				low = mid + 1;
			} else if (midVal > key) {
				high = mid - 1;
			} else {
				return mid;
			}
		}
		// 找不到时定位到最后找的一位下标
		return -(low + 1);
	}

	@org.junit.Test
	private void testQuickSort() {
		int[] array = { 31, 21, 59, 68, 12, 40 };
		quickSort(array, 0, array.length - 1);
	}

	/**
	 * 快速排序
	 * 
	 * @param arry
	 *            查找的数组
	 * @param begin
	 *            开始的位置
	 * @param end
	 *            结束的位置
	 */
	public static void quickSort(int[] arry, int begin, int end) {
		if (end - begin <= 1) {
			return;
		}
		int x = arry[begin];
		int low = begin;
		int high = end;
		// 判断查找的方向
		boolean direction = true;
		L1: while (low < high) {
			// 从右往左找
			if (direction) {
				for (int i = high; i > low; i--) {
					if (arry[i] <= x) {
						arry[low++] = arry[i];
						high = i;
						direction = !direction;
						continue L1;
					}
				}
				high = low;
			} else {
				for (int i = low; i < high; i++) {
					if (arry[i] >= x) {
						arry[high--] = arry[i];
						low = i;
						direction = !direction;
						continue L1;
					}
				}
				low = high;
			}
		}
		arry[low] = x;
		for (int i = 0; i < arry.length; i++) {
			System.out.println(arry[i]);
		}
	}

}
